import java.lang.reflect.Array;
import java.util.Arrays;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.Random;

public class HybridList<E> implements Iterable<E> {
	final static int BEFORE_FIRST = -1, AFTER_LAST = -2;
					
	int size = 0, firstLink, lastLink;
	
	int emptyLinksSize = 0;
	int[] emptyLinks;
	
	int[] link_previous, link_next;
	E[] link_value;
	
	public HybridList( Class<E> elementClass, int initialArraySize ) {
		emptyLinks = new int[ initialArraySize ];
		
		link_previous = new int[ initialArraySize ];
		link_next = new int[ initialArraySize ];
		link_value = (E[]) Array.newInstance( elementClass, initialArraySize );
	}
	
	public void add( E element ) {
		if( link_value.length == size ) {
			int newLength = link_value.length * 2;
			link_previous = Arrays.copyOf( link_previous, newLength );
			link_next = Arrays.copyOf( link_next, newLength );
			link_value = Arrays.copyOf( link_value, newLength );
		}
		
		int newLink;
		if( emptyLinksSize > 0 ) {
			emptyLinksSize--;
			newLink = emptyLinks[ emptyLinksSize ];
		} else {
			newLink = size;
			size++;
		}
		
		if( size == 1 ) {
			firstLink = newLink;
			lastLink = newLink;
			link_previous[ newLink ] = BEFORE_FIRST;
			link_next[ newLink ] = AFTER_LAST;
		} else {
			link_previous[ newLink ] = lastLink;
			link_next[ newLink ] = AFTER_LAST;
			link_next[ lastLink ] = newLink;
		}
	}

	@Override
	public Iterator<E> iterator() {
		return new HybridListIterator<E>( this );
	}
	
	private static class HybridListIterator<E> implements Iterator<E> {
		HybridList<E> list;
		int link, currentLink;
		
		public HybridListIterator( HybridList list ) {
			this.list = list;
			this.link = list.firstLink;
		}
		
		@Override
		public boolean hasNext() {
			return link != AFTER_LAST;
		}

		@Override
		public E next() {
			E value = list.link_value[ link ];
			currentLink = link;
			link = list.link_next[ link ];
			return value;
		}

		@Override
		public void remove() {
			int prevLink = list.link_previous[ currentLink ];
			int nextLink = list.link_next[ currentLink ];
			if( prevLink == BEFORE_FIRST ) {
				list.firstLink = nextLink;
			} else {
				list.link_next[ prevLink ] = list.link_next[ currentLink ];
			}
			if( nextLink == AFTER_LAST ) {
				list.lastLink = prevLink;
			} else {
				list.link_previous[ nextLink ] = list.link_next[ currentLink ];
			}
			
			if( list.emptyLinks.length == list.emptyLinksSize ) {
				list.emptyLinks = Arrays.copyOf( list.emptyLinks, list.emptyLinks.length * 2 );
			}
			list.emptyLinks[ list.emptyLinksSize ] = currentLink;
			list.emptyLinksSize++;
		}
	}
	
	// ================================ Benchmark =============================
	
	public static void main( String[] args ) {
		int iterations = 10000;
		int listSize = 100;
		int addingItemsQuantity = 50;
		
		Random generator = new Random( System.currentTimeMillis() );
		
		Object object = new Object();
		
		LinkedList<Object> linkedList = new LinkedList<Object>();
		HybridList<Object> hybridList = new HybridList<Object>( Object.class, 128 );
						
		for( int n = 0; n < listSize; n++ ){
			linkedList.add( object );
			hybridList.add( object );
		}
		
		Iterable<Object> list = linkedList;
		while( true ) {
			long time = System.currentTimeMillis();
			
			for( int n = 0; n < iterations; n++ ){
				int k = 0;
				for ( Iterator<Object> iterator = hybridList.iterator(); iterator.hasNext(); iterator.next() ) {
					if( k % 3 == 0 ) iterator.remove();
					k++;
				}

				for( int m = 0; m < addingItemsQuantity; m++ ) {
					if( list == linkedList ) {
						linkedList.add( object );
					} else {
						hybridList.add( object );
					}
				}
			}
			
			System.out.println( System.currentTimeMillis() - time );
			if( list == linkedList ) list = hybridList; else break;
		}
	}
}